import java.util.Stack;

class IndexWrongException extends RuntimeException {
    public IndexWrongException() {
    }

    public IndexWrongException(String message) {
        super(message);
    }
}

public class MySingLeList {

    static class ListNode {
        public int value;//结点数据域的值
        public ListNode next;//地址域

        //构造方法
        public ListNode(int vlaue) {
            this.value = vlaue;
        }
    }

    //创建头结点
    public ListNode head;//默认初始值是null

    //创建一个方法实现5个结点
    public void createList() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(12);
        ListNode listNode3 = new ListNode(123);

        //将每个结点链接起来
        listNode1.next = listNode2;
        listNode2.next = listNode3;

        //将头节点指向链表的首个节点
        this.head = listNode1;
    }

    //打印链表当前的数据
    public void disPlay() {
        ListNode cur = this.head;//代替head移动
        while (cur != null) {
            System.out.print(cur.value + " ");
            //找到下一个结点
            cur = cur.next;
        }
        System.out.println();//换行
    }

    //查找key是否存在单链表中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.value == key) {
                return true;//找到
            }
            cur = cur.next;//指向下一个结点
        }
        return false;//没找到
    }

    //在链表中插入一个结点到头部 - 头插法
    public void addStart(int data) {
        ListNode node = new ListNode(data);
        node.next = head;//找到原头结点
        head = node;//原头结点在指向新的头结点
    }

    //尾插法
    public void addEnd(int data) {
        ListNode cur = this.head;
        ListNode node = new ListNode(data);
        //先找到尾结点的位置
        //现在分为情况1：链表为空 - 情况2：链表不为空
        if(cur == null) {
            this.head = node;//直接指向node
        }else {
            while (cur.next != null) {
                cur = cur.next;//找到下一个结点
            }
        }

        //此时cur指向的就是尾结点
        //开始插入
        cur.next = node;
    }

    public ListNode findIndexSubOne(int index) {
        //查找index前一个位置
        ListNode cur = this.head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

    //在链表指定位置插入一个结点
    public void addIndex(int index, int data) {
        //位置不能是负数，不能超过数组的长度
        if (index < 0 || index > size()) {
            System.out.println("index位置不合法！！！");
            throw new IndexWrongException("index位置不合法！！！");
        }

        //这个位置可能在表的中间
        //定义方法来找到index-1的位置
        ListNode node = new ListNode(data);
        ListNode cur = findIndexSubOne(index);//cur就是index-1的位置
        node.next = cur.next;
        cur.next = node;

        //位置可能在表的两端
        //头结点位置
        if (index == 0) {
            addStart(data);
            return;
        }

        //尾结点
        if (index == size()) {
            addEnd(data);
            return;
        }
    }

    //删除第一次出现的key结点
    public void remove(int key) {
        //key的位置要合法.不能超过数组的长度
        //表不能为空
        if (this.head == null) {
            return;
        }

        //结点在头处
        if (this.head.value == key) {
            this.head = this.head.next;
            return;
        }

        //在其他位置
        ListNode cur = findIndexSubOne(key);//调用找到key-1的位置

        //表中可能没有key
        if(cur == null) {
            System.out.println("表中没有key这个结点！！！");
            return;
        }

        //开始删除
        ListNode del = cur.next;
        cur.next = del.next;
    }

    //删除所有的key
    public void removeAllKey(int key) {
        //表不能为空
        if (this.head == null) {
            return;
        }

        //定义两个位置
        ListNode cur = this.head.next;
        ListNode prev = this.head;
        while (cur != null) {
            if (key == cur.value) {
                //改指向删除
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }

        //如果表的第一结点是key
        if (this.head.value == key) {
            this.head = this.head.next;
        }
    }

    //递归实现逆序打印链表的结点
    public void disPlay1() {
        ListNode cur = this.head;
        //链表为空
        if (this.head == null) {
            return;
        }

        //只有一个结点
        if (cur.next == null) {
            System.out.print(this.head.value + " ");
            return;
        }

        //一个结点以上的情况
        disPlay(this.head.next);//指向下一个
        System.out.print(this.head.value + " ");
    }

    //栈实现逆序打印链表的结点
    public void disPlay2(ListNode head) {
        ListNode cur = this.head;
        Stack<Integer> stack = new Stack<>();
        //链表是空的
        if (this.head == null) {
            return;
        }

        //遍历链表将结点压入
        while (cur != null) {
            stack.push(cur);//将cur指向的结点删除
            cur = cur.next;//指向下一个
        }

        //弹出
        while (!stack.empty()) {
            stack.pop();
            System.out.print(cur.value + " ");
        }
    }

    //清空链表
    public void clear() {
        this.head = null;
    }

    //求链表的长度 - 节点个数
    public int size() {
        int count = 0;//记录节点个数
        ListNode cur = this.head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public static void main(String[] args) {

    }

    public static void main1(String[] args) {
       MySingLeList mySingLeList = new MySingLeList();

        //测试链表是否创建成功
        mySingLeList.createList();//调式查看

        //测试打印链表数据的方法
        mySingLeList.disPlay();

        //测试key是否存在链表中
        System.out.println(mySingLeList.contains(12));//输出true
        System.out.println(mySingLeList.contains(1234));//输出false

        //测试头插法
        mySingLeList.addStart(21);
        mySingLeList.addStart(321);
        mySingLeList.disPlay();

        //测试尾插法
        mySingLeList.addEnd(1234);
        mySingLeList.disPlay();

        //测试在指定位置插入一个结点
        mySingLeList.addIndex(3, 99);
        mySingLeList.disPlay();

        //测试删除第一次出现的key结点
        mySingLeList.remove(3);
        mySingLeList.disPlay();

        //测试删除所有的key
        mySingLeList.removeAllKey(1234);
        mySingLeList.disPlay();

        //测试求链表的长度
        System.out.println(mySingLeList.size());
    }
}
